# 134. 加油站
# 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
# 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
# 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

# 一句话概括：
# 如果x到达不了y+1，那么x-y之间的点也不可能到达y+1，
# 因为中间任何一点的油都是拥有前面的余量的，所以下次遍历直接从y+1开始
def canCompleteCircuit(gas, cost):
    """
    :type gas: List[int]
    :type cost: List[int]
    :rtype: int
    """
    gas_length = len(gas)
    # 存储经过每个加油站，剩余的油量
    left = [0] * gas_length
    for gas_index in range(gas_length):
        left[gas_index] = gas[gas_index] - cost[gas_index]
    n = 0
    while n < gas_length:
        temp = 0
        for count in range(1, gas_length + 1):
            temp = temp + left[(n + count - 1) % gas_length]
            if temp < 0:
                n = n + count
                break
        if temp >= 0:
            return n
    return -1


# 超出时间限制，时间复杂度过高
def canCompleteCircuit_overTime(gas, cost):
    """
    :type gas: List[int]
    :type cost: List[int]
    :rtype: int
    """
    gas_length = len(gas)

    for gas_index in range(gas_length):
        # 判断是否可以作为起始点
        if gas[gas_index] >= cost[gas_index]:
            # 剩余的油量
            left_gas = 0
            for new_index in range(gas_length):
                calculate_index = (gas_index + new_index) % gas_length

                gas_count = gas[calculate_index]
                cost_count = cost[calculate_index]

                left_gas = left_gas + gas_count - cost_count

                if left_gas < 0:
                    break
            if left_gas < 0:
                continue
            else:
                return gas_index
    return -1


gas_1 = [1, 2, 3, 4, 5]
cost_1 = [3, 4, 5, 1, 2]
result = canCompleteCircuit(gas_1, cost_1)
print(f"result:{result}")

gas_2 = [2, 3, 4]
cost_2 = [3, 4, 3]
result = canCompleteCircuit(gas_2, cost_2)
print(f"result:{result}")
